package com.cj.user.service.datastructure;

/**
 * @Author cheng jun
 * @Description: 二叉搜索树
 * @Date 2021/7/16 18:08
 */
public class BinarySearchTree {

    /**
     * 插入的数字
     */
    private int data;

    /**
     * 左节点
     */
    private BinarySearchTree left;

    /**
     * 右节点
     */
    private BinarySearchTree right;

    public BinarySearchTree(int data) {
        this.data = data;
        left = null;
        right = null;
    }

    /**
     * 插入
     * @param root
     * @param data
     */
    public void insert(BinarySearchTree root, int data) {
        if (root.data < data) {
            // 根节点小于插入的数字，插入到右节点
            if (null == root.right) {
                // 如果右节点为空
                root.right = new BinarySearchTree(data);
            } else {
                insert(root.right, data);
            }
        } else {
            // 根节点大于插入的数字，插入到左节点
            if (null == root.left) {
                // 如果左节点为空
                root.left = new BinarySearchTree(data);
            } else {
                insert(root.left, data);
            }
        }
    }


    /**
     * 前序遍历
     * @param root
     */
    public void beforeOrder(BinarySearchTree root) {
        if (null != root) {
            System.out.println(root.data);
            middleOrder(root.left);
            middleOrder((root.right));
        }
    }

    /**
     * 中序遍历
     * @param root
     */
    public void middleOrder(BinarySearchTree root) {
        if (null != root) {
            middleOrder(root.left);
            System.out.print(root.data + ",");
            middleOrder((root.right));
        }
    }

    /**
     * 后序遍历
     * @param root
     */
    public void behindOrder(BinarySearchTree root) {
        if (null != root) {
            middleOrder(root.left);
            middleOrder((root.right));
            System.out.println(root.data);
        }
    }

    /**
     * 冒泡排序
     * @param
     */
    /*public void bubbleSort(int[] array) {
        for(int i=0;i<array.length-1;i++)
        {
            for(int j=0;j<array.length-1-i;j++)
            {
                if(array[j]>array[j+1])
                {
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
        }
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ",");
        }
    }*/

    public static void main(String[] args) {
        int[] data = {5, 3, 6, 9, 0, 8, 4};
        long start = System.currentTimeMillis();
        BinarySearchTree root = new BinarySearchTree(data[0]);
        for (int i = 1; i < data.length; i++) {
            root.insert(root, data[i]);
        }
        System.out.println("中序遍历:");
        root.middleOrder(root);
        long end = System.currentTimeMillis();
        System.out.println();
        System.out.println("二叉搜索树中序遍历所耗费时间:" + (end - start));

        /*long start2 = System.currentTimeMillis();
        root.bubbleSort(data);
        long end2 = System.currentTimeMillis();
        System.out.println();
        System.out.println("冒泡排序所耗费时间:" + (end2 - start2));*/
    }
}
